// poj3481
// 题解：题目比较水，可以用set，注意要删除一个rbegin，可以如下写的。
//       que.erase(--que.rbegin().base());
//
// run: $exec < input
#include <cstdio>
#include <utility>
#include <set>

int const maxp = 10000001;
std::pair<int, int> const max = std::make_pair(maxp, 0);
std::pair<int, int> const min = std::make_pair(0, 0);

typedef std::set<std::pair<int, int> > set_type;
typedef set_type::iterator set_iter;

set_type que;

int main()
{
	for (int x, k, p; std::scanf("%d", &x) && x; ) {
		if (x == 1) {
			std::scanf("%d %d", &k, &p);
			que.insert(std::make_pair(p, k));
			continue;
		}
		if (x == 2) {
			if (que.empty())
				std::printf("0\n");
			else {
				std::printf("%d\n", que.rbegin()->second);
				que.erase(--que.rbegin().base());
			}
			continue;
		}
		if (x == 3) {
			if (que.empty())
				std::printf("0\n");
			else {
				std::printf("%d\n", que.begin()->second);
				que.erase(que.begin());
			}
			continue;
		}
	}
}

